//! K紧邻算法
//! 在linfa_nn库， 一共有三种用来搜索的基本数据结构，分别为BallTree，KdTree和
//! LinearSearch.我们可以任意选择任意的数据结构去实现knn算法。CommonNearestNeighbour是
//! 这三种数据结构的枚举.
//! NearestNeighbour这个trait用来生成索引结构，
//! NearestNeighbourIndex这个trait用来搜索紧邻。
//! linfa_nn::distance中还有计算距离的各种范数。L1Dist: 曼哈顿算法c = |x1 - x2| + |y1 - y2|
//! L2Dist: Euclidean 欧几里得算法 c = √(x1 - x2)*(x1-x2) + (y1-y2)*(y1-y2)
//! LInfDist: Chebyshev 切比雪夫算法： 二个点之间的距离定义是其各坐标数值差绝对值的最大值
//! LpDist：Minkowsky 闵可夫斯基 [（x1-x2）p次方 + (y1-y2)的p次方]开p次方根
//!     当p=1时，就是曼哈顿距离
//!     当p=2时，就是欧氏距离
//!     当p→∞时，就是切比雪夫距离
//!

use linfa_nn::{distance::Distance, NearestNeighbour};
use ndarray::prelude::*;
use noisy_float::{checkers::NumChecker, prelude::*, NoisyFloat};

pub use linfa_nn::{
    distance::{L1Dist, L2Dist, LInfDist, LpDist},
    BallTree, KdTree, LinearSearch,
};

/// knn近邻算法的统一结构体
pub struct Knn<'a, N> {
    // 样本的features
    x_train: &'a Array2<f64>,
    // 样本的targets
    y_train: &'a Array1<f64>,
    // 要选择的索引数据结构
    index_type: N,
}

impl<'a, N> Knn<'a, N>
where
    N: NearestNeighbour,
{
    // 把训练样本的features和targets喂给我们的模型
    pub fn fit(x_train: &'a Array2<f64>, y_train: &'a Array1<f64>, index_type: N) -> Self {
        Self {
            x_train,
            y_train,
            index_type,
        }
    }

    // 用模型进行预测
    // x_test: 训练样本
    // k: 选择k个距离相近的样本
    // norm: 要使用的范数
    pub fn predict<L: 'a + Distance<f64>>(
        &self,
        x_test: &'a Array2<f64>,
        k: usize,
        norm: L,
    ) -> anyhow::Result<Array1<f64>> {
        if self.x_train.axis_iter(Axis(0)).len() < k {
            panic!("k is too large");
        }
        let dis = self.index_type.from_batch(self.x_train, norm.clone())?;
        let mut y_predict = Vec::with_capacity(x_test.axis_iter(Axis(0)).len());
        for v in x_test.axis_iter(Axis(0)) {
            // ret数组是按照距离从小到大排序的
            let ret = dis.k_nearest(v, k)?;
            // 计算距离
            let distance_vec = self.distances(v, &ret, norm.clone());
            // 对距离进行投票
            let y = self.vote(&distance_vec);
            y_predict.push(y);
        }
        Ok(Array1::from_vec(y_predict))
    }

    // 计算near里面所有的样本到point的距离的列表
    fn distances<L: 'a + Distance<f64>>(
        &self,
        point: ArrayView1<f64>,
        nears: &[(ArrayView1<f64>, usize)],
        norm: L,
    ) -> Vec<(NoisyFloat<f64, NumChecker>, NoisyFloat<f64, NumChecker>)> {
        let mut ret = Vec::with_capacity(nears.len());
        for v in nears {
            let dis = norm.distance(v.0, point);
            ret.push((n64(dis), n64(self.y_train[v.1])));
        }
        //ret数组是按照距离从小到大排序的(12, y_train的值), (13, y_train的值)
        ret
    }

    // 对距离进行投票表决,最终选举出最佳的预测值
    fn vote(&self, dis: &[(NoisyFloat<f64, NumChecker>, NoisyFloat<f64, NumChecker>)]) -> f64 {
        // 因为dis是按照距离从小到大排序的， 所以，我们排序成[[(1,y_train), (1, y_train), (1, ytrain)], [(2, ytrain), (2, ytrain), (2, yrain)]]
        let mut current_dis = dis[0].0;
        let mut dis_vecs = vec![];
        let mut tmp = vec![];
        for v in dis {
            if v.0 != current_dis {
                dis_vecs.push(tmp);
                tmp = vec![];
                current_dis = v.0;
            }
            tmp.push(v.clone());
        }
        dis_vecs.push(tmp);
        // [[(1,y_train), (1, y_train), (1, ytrain)], [(2, ytrain), (2, ytrain), (2, yrain)]]， 我们把y值相同的计数，进行投票表决
        let mut max_y = dis_vecs
            .into_iter()
            .map(|mut x| {
                let max = Self::inner_vote(&mut x);
                let dis_sum = (1f64 / max.0.const_raw()) * max.2 as f64;
                (max.1, n64(dis_sum))
            })
            .collect::<Vec<_>>();
        max_y.sort_by(|a, b| b.1.cmp(&a.1));
        max_y[0].0.const_raw()
    }

    fn inner_vote(
        vec: &mut [(NoisyFloat<f64, NumChecker>, NoisyFloat<f64, NumChecker>)],
    ) -> (
        NoisyFloat<f64, NumChecker>,
        NoisyFloat<f64, NumChecker>,
        usize,
    ) {
        vec.sort_by(|a, b| a.1.cmp(&b.1));
        let mut current = vec[0];
        let mut count = 0;
        let mut votes = vec![];
        for v in vec {
            if v.1 == current.1 {
                count += 1;
            } else {
                votes.push((current.0, current.1, count));
                count = 1;
                current = *v;
            }
        }
        votes.push((current.0, current.1, count));
        votes.sort_by(|a, b| b.2.cmp(&a.2));
        votes[0]
    }
}
